package com.atguigu.HorseChessBoard;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author tbwtbw
 * @create 2021-11-28 11:15
 */
public class horse {

    private static int X;//列数
    private static int Y;//行数
    private static boolean[] visited;
    private static int step = 1;

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int row = 1;
        int column = 1;
        int[][] chessboard = new int[Y][X];

        visited = new boolean[X * Y];//初始值都是false
        horse horse = new horse();
        //测试一下耗时
        long start = System.currentTimeMillis();
        horse.Traverse(chessboard, row - 1, column - 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时: " + (end - start) + " 毫秒");

        //输出棋盘的最后情况
        for(int[] rows : chessboard) {
            for(int step: rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
        //1	    8	11	16	3	18	13	64
        //10	27	2	7	12	15	4	19
        //53	24	9	28	17	6	63	14
        //26	39	52	23	62	29	20	5
        //43	54	25	38	51	22	33	30
        //40	57	42	61	32	35	48	21
        //55	44	59	50	37	46	31	34
        //58	41	56	45	60	49	36	47
    }

    public void Traverse(int[][] chessboard, int row, int column){//传入马儿初始行列

        chessboard[row][column] = step++;
        visited[row * X + column] = true;
        ArrayList<Point> nextSteps = nextSteps(new Point(column, row));
        nextSteps.sort((Comparator.comparingInt(o -> nextSteps(o).size())));//每次选下一步能走位置少的位置跳


        while (!nextSteps.isEmpty()){
            Point point = nextSteps.remove(0);
            if (!visited[point.y * X + point.x])
                Traverse(chessboard,point.y,point.x);
        }

        if (step <= X * Y){//step = 65才退出，说明64已经摆好
            chessboard[row][column] = 0;
            visited[row * X + column] = false;
            step--;//到这里说明摆不了了，所以要减1去摆上一个位置，比如说我63已经摆好，要摆64，结果64摆不了，也就是nextsteps没有
            //说明当前这个63摆得不对，我就要step-- 重新去摆63的位置。由于step是全局变量，一旦到65后就一直是65，所以之后回溯的时候都不会进行判断，
            //一直递归回到栈顶，就不需要finish变量了
        }
    }

    public static ArrayList<Point> nextSteps(Point curPoint){//返回马儿下一步能走的位置
        ArrayList<Point> list = new ArrayList<>();

        Point point = new Point();
        //x 是列
        if ((point.x = curPoint.x - 2) >= 0 && (point.y = curPoint.y - 1) >= 0){
            list.add(new Point(point));
        }
        //判断马儿可以走6这个位置
        if((point.x = curPoint.x - 1) >=0 && (point.y=curPoint.y-2)>=0) {
            list.add(new Point(point));
        }
        //判断马儿可以走7这个位置
        if ((point.x = curPoint.x + 1) < X && (point.y = curPoint.y - 2) >= 0) {
            list.add(new Point(point));
        }
        //判断马儿可以走0这个位置
        if ((point.x = curPoint.x + 2) < X && (point.y = curPoint.y - 1) >= 0) {
            list.add(new Point(point));
        }
        //判断马儿可以走1这个位置
        if ((point.x = curPoint.x + 2) < X && (point.y = curPoint.y + 1) < Y) {
            list.add(new Point(point));
        }
        //判断马儿可以走2这个位置
        if ((point.x = curPoint.x + 1) < X && (point.y = curPoint.y + 2) < Y) {
            list.add(new Point(point));
        }
        //判断马儿可以走3这个位置
        if ((point.x = curPoint.x - 1) >= 0 && (point.y = curPoint.y + 2) < Y) {
            list.add(new Point(point));
        }
        //判断马儿可以走4这个位置
        if ((point.x = curPoint.x - 2) >= 0 && (point.y = curPoint.y + 1) < Y) {
            list.add(new Point(point));
        }

        return list;
    }
}
